package q268_missingNumber;

public class Solution_3 {
    /*
    数组中共有n个数字 而我们期望出现的是n + 1个数字
    可以使用异或运算来找出没出现的数字（效率最高）
    根据出现的次数的奇偶性，可以使用按位异或运算得到丢失的数字。
    对于一个数有 x ^ x = 0 ,x ^ 0 = x
    所以我们利用一个数对数组中所有数进行异或运算
    然后再对0 - n中每个数进行异或运算 除了没有出现的数之外 每个数都出现了两次
    因此最后剩下的数就是没有出现的数
     */
    public int missingNumber(int[] nums) {
        int xor = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            xor ^= nums[i];
        }
        for (int i = 0; i <= n; i++) {
            xor ^= i;
        }
        return xor;
    }

}
